//https://leetcode.cn/problems/Jf1JuT/

class Solution {
    unordered_map<char, unordered_set<char>> edges;
    unordered_map<char, int> in;
    bool cheak = false;
public:
    string alienOrder(vector<string>& words)
    {
        //初始化入度
        int n = words.size();
        for (auto& e : words)
        {
            for (auto& ch : e)
            {
                in[ch] = 0;
            }
        }

        //建图
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                add(words[i], words[j]);
                if (cheak) return "";
            }
        }

        //拓扑排序
        queue<char> q;
        for (auto& [a, b] : in)
        {
            if (b == 0)
                q.push(a);
        }

        string ret;
        while (q.size())
        {
            char t = q.front();
            q.pop();
            ret += t;

            for (auto& e : edges[t])
            {
                in[e]--;
                if (in[e] == 0)
                    q.push(e);
            }

        }

        //检查是否带环
        for (auto [a, b] : in)
        {
            if (b) return "";
        }

        return ret;
    }

    void add(string& s1, string& s2)
    {
        int sz = min(s1.size(), s2.size());
        int i = 0;
        for (; i < sz; i++)
        {
            if (s1[i] != s2[i])
            {
                if (!edges.count(s1[i]) || !edges[s1[i]].count(s2[i]))
                {
                    edges[s1[i]].insert(s2[i]);
                    in[s2[i]]++;
                }
                break;
            }

        }

        if (i == s2.size() && i < s1.size())
        {
            cheak = true;
        }
    }
};